package demo1;

import java.util.ArrayList;

public class Code02_IsBST {

	public static class TreeNode {
		public int value;
		public TreeNode left;
		public TreeNode right;

		public TreeNode(int data) {
			this.value = data;
		}
	}

	public static boolean isBST1(TreeNode head) {
		if (head == null) {
			return true;
		}
		ArrayList<TreeNode> arr = new ArrayList<>();
		in(head, arr);
		for (int i = 1; i < arr.size(); i++) {
			if (arr.get(i).value <= arr.get(i - 1).value) {
				return false;
			}
		}
		return true;
	}

	public static void in(TreeNode head, ArrayList<TreeNode> arr) {
		if (head == null) {
			return;
		}
		in(head.left, arr);
		arr.add(head);
		in(head.right, arr);
	}

	public static boolean isBST2(TreeNode head) {
		if (head == null) {
			return true;
		}
		return process(head).isBST;
	}

	public static class Info{
		public boolean isBST ;
		public int max;
		public int min;

		public Info(boolean isBST,int max,int min){
			this.isBST = isBST;
			this.max = max;
			this.min = min;
		}
	}

	public static Info process(TreeNode head){
		if(head==null) return null;
		Info leftInfo = process(head.left);
		Info rightInfo = process(head.right);
		int max = head.value;
		int min = head.value;
		if(leftInfo!=null){
			max = Math.max(max, leftInfo.max);
			min = Math.min(min, leftInfo.min);
		}
		if(rightInfo!=null){
			max = Math.max(max, rightInfo.max);
			min = Math.min(min, rightInfo.min);
		}
		boolean isBST = true;
		if(leftInfo!=null&&!leftInfo.isBST){
			isBST = false;
		}
		else if(leftInfo!=null&&leftInfo.max>= head.value){
			isBST = false;
		}
		else if(rightInfo!=null&&!rightInfo.isBST){
			isBST = false;
		}
		else if(rightInfo!=null&&rightInfo.min<= head.value){
			isBST = false;
		}
		return new Info(isBST,max,min);
	}





//	public static class Info {
//		public boolean isBST;
//		public int max;
//		public int min;
//
//		public Info(boolean i, int ma, int mi) {
//			isBST = i;
//			max = ma;
//			min = mi;
//		}
//
//	}
//
//	public static Info process(Node x) {
//		if (x == null) {
//			return null;
//		}
//		Info leftInfo = process(x.left);
//		Info rightInfo = process(x.right);
//		int max = x.value;
//		if (leftInfo != null) {
//			max = Math.max(max, leftInfo.max);
//		}
//		if (rightInfo != null) {
//			max = Math.max(max, rightInfo.max);
//		}
//		int min = x.value;
//		if (leftInfo != null) {
//			min = Math.min(min, leftInfo.min);
//		}
//		if (rightInfo != null) {
//			min = Math.min(min, rightInfo.min);
//		}
//		boolean isBST = true;
//		if (leftInfo != null && !leftInfo.isBST) {
//			isBST = false;
//		}
//		if (rightInfo != null && !rightInfo.isBST) {
//			isBST = false;
//		}
//		if (leftInfo != null && leftInfo.max >= x.value) {
//			isBST = false;
//		}
//		if (rightInfo != null && rightInfo.min <= x.value) {
//			isBST = false;
//		}
//		return new Info(isBST, max, min);
//	}

	// for test
	public static TreeNode generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static TreeNode generate(int level, int maxLevel, int maxValue) {
		if (level > maxLevel || Math.random() < 0.5) {
			return null;
		}
		TreeNode head = new TreeNode((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	public static void main(String[] args) {
		int maxLevel = 4;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
			TreeNode head = generateRandomBST(maxLevel, maxValue);
			if (isBST1(head) != isBST2(head)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");
	}

}